package demo.DataStrucAndAlgo.AlgorithmOfTen;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/13-08-13-17:49
 * @Description：demo.DataStrucAndAlgo.AlgorithmOfTen  回溯算法
 */
/*
回溯算法
    回溯算法是一种局部暴力的枚举算法
    循环中，若条件满足，进入递归，开启下一次流程，若条件不满足，就不进行递归，转而进行
    上一次的流程。这个过程称之为递归
    结构：在一个循环中，嵌套一个条件判断，条件判断中，嵌套一个自身递归。三层结构，相互嵌套，缺一不可
    e.g.
        在一个7*7的棋盘中，指定某个起始位置，如何才能使遵循马走日规则的棋子，将36个棋盘位置全部走一遍，其走过的位置不能再走
    马走日是规则，极限情况下，一个棋子有如下图8种可选方案，每种方案都对应着一个if语句，8种方案组成我们马走日的行走策略
    采用回溯算法需要先找到当前棋子所有的可选方案（代码中由next方法实现），然后遍历每个方案，每个方案采取上述相同的流程
    ，直到找到可以符合题目要求的行走路线，或者是被判定无法再行走而终止递归（代码中由 traversalChessboard 方法实现）
 */
public class backTrace {
    private static int X;  //棋盘宽度
    private static int Y;  //棋盘高度
    private static boolean[] visited;  //用于记录棋盘被访问情况
    private static boolean finish = false;    //用于记录是否完成马踏棋盘

    public static void main(String[] args) {
        //初始化数据
        X = Y = 7;
        int row = 3, col = 3;    //起始点为3行3列
        visited = new boolean[X*Y];
        int[][] chessBoard = new int[X][Y];

        traversalChessBoard(chessBoard,row-1,col-1,1);

        //输出结果
        for (int[] temp:chessBoard) {
            System.out.println(Arrays.toString(temp));
        }

        }

    /**
     * 马踏棋盘解决方案主体（回溯算法）
     * @param chessBoard   棋盘
     * @param row    行数
     * @param col    列数
     * @param step   步数
     */
    public static void traversalChessBoard(int[][] chessBoard, int row, int col, int step) {
        chessBoard[row][col] = step;     //将步数赋值到对应棋盘位置上
        visited[row*X+col] = true;       //将该处设置为已访问（row被-1）
        //调用next来获得可选方案，注意next方法处理的时候先处理列，再处理行，所以传入的point对象为point(y,x)
        ArrayList<Point> allow = next(new Point(col,row));     //用于存储目前可以进入的棋盘（存储可选方案）
        sort(allow);   //!!!对结果进行排序优化！！！
        //回溯算法核心：回溯式的找到所有位置
        while(!allow.isEmpty()){        //可选方案非空时
            Point p = allow.remove(0);   //拿取可选方案中的头一个位置
            if(!visited[p.y*X+p.x]){       //当该方案位置没有被访问时
                traversalChessBoard(chessBoard,p.y,p.x,step+1);    //以方案位置再进行上述查找
            }
        }
        //终止回溯条件
        if(step < X*Y && !finish){     //当步数不够且未完成所有位置时
            chessBoard[row][col]=0;      //初始化本次回溯过程中棋盘数据
            visited[row*X+col]=false;    //将该位置仍然设置为未访问
        }else {    //解决问题，可以跳出回溯了
            finish = true;
        }
    }

    private static void sort(ArrayList<Point> allow) {
        allow.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return next(o1).size()-next(o2).size();
            }
        });
    }

    /**
     * 把当前位置棋子的所有可访问棋盘位置以集合的形式输出
     * @param curPoint   当前棋子
     * @return       当前位置棋子的所有可访问棋盘位置
     */
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> allowPoint = new ArrayList<>();   //存储当前位置可以进入的位置
        Point allow = new Point();
        //下面的策略是先计算列，再计算行
        //走位置5
        if((allow.x = curPoint.x-2) >= 0 && (allow.y = curPoint.y-1)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置6
        if((allow.x=curPoint.x-1)>=0 && (allow.y=curPoint.y-2)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置7
        if((allow.x=curPoint.x+1)<X && (allow.y=curPoint.y-2)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置0
        if((allow.x=curPoint.x+2)<X && (allow.y=curPoint.y-1)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置1
        if((allow.x=curPoint.x+2)<X && (allow.y=curPoint.y+1)<Y){
            allowPoint.add(new Point(allow));
        }
        //走位置2
        if((allow.x=curPoint.x+1)<X && (allow.y=curPoint.y+2)<Y){
            allowPoint.add(new Point(allow));
        }
        //走位置3
        if((allow.x=curPoint.x-1)>=0 && (allow.y=curPoint.y+2)<Y){
            allowPoint.add(new Point(allow));
        }
        //走位置4
        if((allow.x=curPoint.x-2)>=0 && (allow.y=curPoint.y+1)<Y){
            allowPoint.add(new Point(allow));
        }
        return allowPoint;
    }
}
